#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

// 定义顺序表结构
typedef struct {
    int *data; // 数据存储数组的指针
    int length; // 当前长度
    int capacity; // 容量
} SeqList;

// 初始化顺序表
void initSeqList(SeqList *list, int capacity) {
    list->data = (int *)malloc(capacity * sizeof(int));
    list->length = 0;
    list->capacity = capacity;
}

// 在顺序表末尾插入元素
void append(SeqList *list, int value) {
    if (list->length >= list->capacity) {
        // 扩容
        list->capacity *= 2;
        list->data = (int *)realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->length++] = value;
}

// 释放顺序表
void freeSeqList(SeqList *list) {
    free(list->data);
    list->length = 0;
    list->capacity = 0;
}

// 约瑟夫环问题的求解函数
int* josephus_circle(int n, int m, int *length) {
    SeqList list;
    initSeqList(&list, n);
    for (int i = 1; i <= n; i++) {
        append(&list, i);
    }

    int *result = (int *)malloc(n * sizeof(int));
    int idx = 0;
    while (list.length > 0) {
        idx = (idx + m - 1) % list.length;
        result[(*length)++] = list.data[idx];
        // 删除出列的人
        for (int i = idx; i < list.length - 1; i++) {
            list.data[i] = list.data[i + 1];
        }
        list.length--;
    }

    freeSeqList(&list);
    return result;
}

int main() {
    SetConsoleOutputCP(65001);
    int n, m;
    printf("请输入总人数n：");
    scanf("%d", &n);
    printf("请输入报数m：");
    scanf("%d", &m);

    int length = 0;
    int *out_sequence = josephus_circle(n, m, &length);

    printf("出列编号序列：");
    for (int i = 0; i < length; i++) {
        printf("%d ", out_sequence[i]);
    }
    printf("\n");

    free(out_sequence);

    return 0;
}
